Various encoding formats for encoding an image are known. The particular techniques embodied by these formats vary depending on the relative importance of various factors in the resulting encoded image, such as whether the encoding should be lossless, the desired data size of the resulting encoding image and the overall quality of the encoded image. A widely used and well known set of encoding formats for images are those defined by the JPEG group. However, predetermined encoding formats such as JPEG are not suitable for all applications, in particular those in which random access to areas of pixels in the encoded image is required. This may for example be the case when the encoded image provides a compressed texture to be used in graphics applications. This is because encoding formats such as JPEG rely on techniques which encode blocks of pixels within an image with respect to previous blocks within the same image. Whilst this enables a higher degree of data compression, this approach requires the image to be decoded as a whole and hence such encoding formats are not suitable for applications such as texture rendering, which require random access to subsections of a given image.
Consequently, it is known to encode images according to predetermined encoding formats which do allow such random access. Typically, in such encoding formats, the image is encoded in blocks of pixels (e.g. 4×4) representing the smallest units of the image which can be individually encoded and decoded. One known technique in such encoding formats is to represent the block of pixels by a base colour and a set of luminance offsets with respect to that base colour. In other words, for each block encoded in this manner, only one colour is defined for all of the pixels, with the luminance of each pixel being given as an offset from that base colour. This generally produces an acceptable image quality, because the human eye is less sensitive to local chrominance variation than to local luminance variation.
However, a problem associated with generating encoded images according to such encoding formats (of which the ETC format (Ericsson Texture Compression) is one example) is the processing time required to generate the compressed (encoded) images. For example, when using existing tools to create ETC compressed textures the processing time can be around 300 to 400 pixels per second, or 30 minutes to one hour for a typical texture, for the highest quality supported by those tools. This lengthy processing time results from the searching which is performed within the available encoding space to find the best combination of base colour and luminance offsets for each block of pixels. To produce the highest quality compressed textures the search is multi-dimensional and extensive, resulting in these long processing times. Such long processing times however are unacceptable when developing and testing graphics applications, since applications may include dozens or hundreds of textures, and developers need to be able to assess the quality of the compressed textures during development.
FIG. 1A schematically illustrates a block of 4×4 pixels 10. Typically, when such a block of pixels is encoded according to encoding formats such as ETC, each block is in fact encoded in terms of two half-blocks adjacent to one another. As illustrated in FIG. 1A the block of pixels 10 may be divided by a vertical split into the two half-blocks. Equally, the same block of pixels may be divided into two half-blocks by means of a horizontal split.
The ETC encoding format defines eight tables of luminance offsets as illustrated in FIG. 1B. Hence, a base colour is defined for each half-block, and the eight pixels in that half-block are encoded by means of one three bit table number and eight two bit table entry numbers.
Two varieties of encoding are defined according to the ETC standard, namely absolute encoding and differential encoding, as illustrated in FIG. 1C. Each results in the block of pixels being encoded as a single 64 bit value. In absolute encoding, each half-block is independently encoded. The base colour for each half-block is encoded as a 12 bit (444) RGB value, and the encoding of the whole block is represented by 24 bits giving the R, G and B components of the base colours for the first and second half-blocks making up this block. This is followed by two three bit values giving the luminance offset table used for each half-block. The “diff” bit indicates whether this block has been encoded using absolute or differential encoding. The “flip” bit indicates whether the block has been split horizontally or vertically into half-blocks. Finally, the 16 individual pixels of the two half-blocks are each represented by two bits giving their corresponding entry in the selected table. The encoding format groups these as 16 MSBs and 16 LSBs.
The differential encoding is similarly defined, except that here the base colour of the second half-block is defined as an offset with respect to the first half-block. Hence, the first half-block base colour is given as a 15 bit (555) RGB value and the R, G and B offsets for the second half-block are each given as three bit offsets. This enables greater precision in defining the base colours, but only if the base colours of the half-blocks are close enough to one another to be represented by these three bit offsets. Otherwise the absolute encoding is used.
The 24 bits used to encode the base colours for the half-blocks correspond to a predetermined set of base colours which may be defined in the encoding. This predetermined set of base colours is schematically illustrated in FIG. 2A. Note that for clarity of illustration only a two dimensional representation is shown in which only the R and G components are shown (the B component in the third dimension being omitted). The base colour selected for the encoding of a given half-block is typically selected with reference to the average colour of the pixels in the half-block. Since the encoded pixels are encoded as luminance offsets with respect to a selected base colour, the diagonal lines (luminance lines) in FIG. 2A constrain where encoded pixels may lie in this colour space.
As illustrated in FIG. 2A, there is more than one way to choose the base colour from the predetermined set of base colours available for a given calculated average colour. Base colour 30 is the nearest base colour on the nearest luminance line, whilst base colour 40 is the geometrically nearest base colour.
FIG. 2B graphically illustrates the encoding of a given pixel value by means of a luminance offset from a base colour. The luminance offset (selected from a predefined table of luminance offsets) gives the position in this colour space of the compressed pixel colour relative to the base colour. The distance between the compressed pixel colour and the original pixel colour gives the encoding error for this pixel.
FIG. 3 shows the search range performed by an existing ETC compression algorithm for the base colour of each half-block of pixels. Having selected an initial base point (i.e. base colour) in dependence on the average colour of the pixels of the half-block, a search is performed in a volume of base points around that starting base point to see if an improved encoding can be found. In the high quality version of the compression, a 7×7×7 search volume is explored (represented as a 7×7 search area in the 2D representation shown). Amongst these the encoding which minimises the overall encoding error for the half-block is selected. It is the iterative process of calculating the best encoding for all eight possible tables for each of these 7×7×7 (i.e. 343) candidate base points which results in the lengthy processing procedure for existing compression tools.
Descriptions of some existing approaches to such image encoding/compression can be found in:
the presentation “iPACKMAN—High-Quality, Low Complexity Texture Compression for Mobile Phones” by Jacob Strom and Tomas Akenine-Moller (retrieved from http://www.graphicshardware.org/previous/www—2005/presentations/strom-ipackman-gh05.ppt) which describes the ETC compression format;
in the full Khronos standard for the ETC format (available at http://www.khronos.org/registry/gles/extensions/OES/OES_compressed_ETC1_RGB8_texture.txt);
in the paper “Real Time DXT Compression”, J. M. P. van Waveren, May 2006 (http://cache-www.intel.com/cd/00/00/32/43/324337—324337.pdf); and
in a description of NVIDIA texture tools (retrieved on 12 Nov. 2010 from: http://code.google.com/p/nvidia-texture-tools/wiki/ApiDocumentation).
However, the above described lengthy processing times are prevalent in the prior art approaches and accordingly, it would be desirable to provide an improved technique for generating high quality encodings, which require less processing time.